题解 P5400 【[CTS2019]随机立方体】

发表于 | 更新于

$Description$

有一个$n\times m\times l$的立方体，立方体中每个格子上都有一个数，如果某个格子上的数比三维坐标至少有一维相同的其他格子上的数都要大的话，我们就称它是极大的。

现在将$1\sim n\times m\times l$这$n\times m\times l$个数等概率随机填入$n\times m\times l$个格子（即任意数字出现在任意格子上的概率均相等），使得每个数恰出现一次，求恰有$k$个极大的数的概率。答案对$998244353$取模。

$Solution$

考虑容斥

以下把$n\times m\times l$的立方体中$1\times 1\times 1$的单位立方体称为’块‘

设$N=n\times m\times l$

设$f_{i}$表示至少有$i$个极大的数的方案数

$b_{i}~$表示选出$i~$个三维坐标都不相同的点的方案数。($i~$个极大的数)

$g_{i}~$表示和$i~$个极大的数中任意一个至少有一维坐标相同的点的个数。

$h_{i}~$表示将$g_{i}~$个数字分配给$g_{i}$的个点的合法分配的方案数。(合法指的是$i~$个极大的数可以同时存在)

$f_{i}=C_{N}^{g_{i}} \times b_{i} \times h_{i} \times(N-g_{i}) !$

我们先来考虑$b_{i}~:$

如果在$(a,b,c)$钦定了一个极大数，那么$x=a,y=b,z=c$三个平面都不能填极大数了，即原问题变成了一个$(n-1)\times(m-1)\times(l-1)$

所以$:$

$b_{i}=\dfrac{1}{i!}~\prod\limits_{j=0}^{i-1}(n-j) \times(m-j) \times(l-j)$

考虑$g_{i}:$

显然$:g_{i}=N-(n-i) \times(m-i) \times(l-i)($所有块减去所有三维坐标与$i$个极大的数完全不相同的块的个数$)$

考虑$h_{i}$怎么算：

可以发现，这个东西一下子求不来，可以考虑一下递推的方法。

我们先把$g_{i}$个数中最大的数值(这个最大的数值一定是极大数)拿出来，填到对应位置，然后剩下的$g_{i}-g_{i-1}-1$个位置(即这个数值会影响到的所有的块，$g_{i-1}$即不会影响到的块,$-1$即减去自身)，每个位置可以随便选择一个数，方案数为$(g_{i}-g_{i-1}-1)!=\frac{(g_{i}-1)!}{g_{i-1}!}$，然后我们可以发现，剩下的数的填充就是子问题$h_{i-1}$

$h_{i}=\frac{\left(g_{i}-1\right) !}{g_{i-1} !} \times h_{i-1}$

$\quad\,=\prod_{j=0}^{i-1} \frac{\left(g_{j+1}-1\right) !}{g_{j} !} $

注意$:$这个式子是不考虑大小顺序的，所以最后所有的$h_{i}$都要乘上$i!$(注意$:$不能在算的时候乘，会影响后面$h_{i}~$的计算的)

将所有的东西带回去

$f_{i}~=C_{N}^{g_{i}} \times b_{i} \times h_{i} \times(N-g_{i})!$

$\quad\,\,=\frac{N!}{(N-g_{i}) ! g_{i} !} \times b_{i} \times i!\times \prod_{j=1}^{i} \frac{(g_{j}-1)!}{g_{j-1} !} \times(N-g_{i}) !$

我们发现最后算概率的时候要乘上$\frac{1}{N!}$

$f_{i}~=\frac{i!}{g_{i}!} \times b_{i} \times \prod_{j=1}^{i} \frac{(g_{j}-1) !}{g_{j-1}!}$

$\quad\,\,=i! \times b_{i}\times \prod_{j=1}^{i} \frac{(g_{j}-1) !}{g_{j}!}$

$\quad\,\,=i! \times b_{i} \prod_{j=1}^{i} \frac{1}{g_{j}}$

由于

$f_{i}=\sum\limits_{j=i}^{min (n, m, l)} ans_{j}C_{j}^{i}$

最后二项式反演一下有：

$ans_{i}=\sum\limits_{i=k}^{\min (n, m, l)}\times (-1)^{i-k}\times C_{i}^{k}\times f_{i}$
但这样只能得到$80$分 ，我们预处理出来$g_{i}$的前缀积，求最后一项的逆元后可以逆推每一个前缀积的逆元，如当前$1\sim i$的前缀积的逆元为$inv$,那么想得到$1\sim (i-1)$的前缀积，只需将$inv\times i$即可

以下内容为二项式反演证明$:$

$g_{i}=\sum\limits_{j=1}^{i}C_i^j f_{j}$

$f_{i}=\sum\limits_{j=1}^{i}(-1)^{i-j}~ C_{i}^{j}~g_{j}$

证明等式成立相当于证明对于等式右边而言，所有$f_{k}$的系数为$[i==k]$

则$f_{k}$的系数为$\sum\limits_{j=k}^{i}(-1)^{i-j}~C_{i}^{j}~C_{j}^{k}$

化简:

$\sum\limits_{j=k}^{i}(-1)^{i-j} \frac{i !}{j !(i-j) !} \frac{j !}{k !(j-k) !}$

消去$j!$,提出$\frac{i !}{k !}$

$\left(\sum\limits_{j=k}^{i}(-1)^{i-j} \frac{1}{(i-j) !(j-k) !}\right) \frac{i !}{k !}$

乘$(i-k)!$，除$(i-k)!$

$\left(\sum\limits_{j=k}^{i}(-1)^{i-j} \frac{(i-k) !}{(i-j) !(j-k) !}\right) \frac{i !}{k !(i-k) !}$

$\left(\sum_{j=k}^{i}(-1)^{i-j}~C_{i-k}^{j-k}\right)C_{i}^{k}.$

$\sum\limits_{j=k}^{i}(-1)^{i-j}~C_{i-k}^{j-k}=[i==k]$

如果成立,则$:$当$i==k$时，$C_{i}^{k}==1$,所以系数为$1$,当$i!=k$时，前一个式子为$0$，所以系数为$0$

证明$:$当$i!=k$时，前一个式子为$0$

当$i-k$为奇数时，相当于有$i−k+1$个数相加(分别对应取$0$个，取$1$个…取$i - k$个)，一共偶数个，其中第一项与最后一项异号，第二项与倒数第二项异号。。。根据组合数的对称性，和为$0$。

当$i-k$为偶数时，相当于证$:$

$C_{i}^{0}-C_{i}^{1}+C_{i}^{2}-\cdots -C_{i}^{i-1}+C_{i}^{i}=0$

用杨辉三角证明(好像二项式定理也可以证)

原式$=C_{i-1}^{0}-(C_{i-1}^{0}+C_{i-1}^{1})+(C_{i-1}^{1}+C_{i-1}^{2})-\cdots-(C_{i-1}^{i-2}+C_{i-1}^{i-1})+C_{i-1}^{i-1}$

发现最后全抵消掉了，所有原式$=0$

$Code$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <bits/stdc++.h>
#define int long long
#define inf 0x3f3f3f3f
#define mod 998244353
#define N 5000070
using namespace std;
inline int read(){
    int x=0,w=0;char ch=getchar();
    while (!isdigit(ch))w|=ch=='-',ch=getchar();
    while (isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
    return w?-x:x;
}
int ksm(int x,int p){
    int res=1;
    while (p){
        if (p&1)res=res*x%mod;
        x=x*x%mod;p>>=1;
    }
    return res;
}
int jc[N],invc[N],inv[N],g[N],f[N];
inline int C(int m,int n){
    return jc[m]*invc[n]%mod*invc[m-n]%mod;
}
signed main(){
    int T=read();jc[0]=1;
    for (int i=1;i<=N-70;++i)jc[i]=jc[i-1]*i%mod;
    invc[N-70]=ksm(jc[N-70],mod-2);
    for (int i=N-71;i>=0;--i)
        invc[i]=invc[i+1]*(i+1)%mod;
    while (T--){
        int n=read(),m=read(),l=read(),k=read(),ans=0,v=1;
        int t=min(n,min(m,l));
        if (k>t){puts("0");continue;}
        for (int i=1;i<=t;++i){
            g[i]=(n*m%mod*l%mod-(n-i)*(m-i)%mod*(l-i)%mod+mod)%mod;
            v=v*g[i]%mod;
        }
        inv[t]=ksm(v,mod-2);
        for (int i=t-1;i>=0;--i){
            inv[i]=inv[i+1]*g[i+1]%mod;
        }
        v=1;
        for (int i=0;i<t;++i){
            v=v*(n-i)%mod*(m-i)%mod*(l-i)%mod;
            f[i+1]=v*inv[i+1]%mod;
        }
        for (int i=k;i<=t;++i){
            if ((i-k)&1)
                ans=(ans-C(i,k)*f[i]%mod+mod)%mod;
            else ans=(ans+C(i,k)*f[i]%mod)%mod;
        }
        printf("%lld\n",ans);
    }
    return 0;
}